/**
 * Represente une matrice binaire de taille ai*s
 * @author Lydie Nguyen
 */
class Matrice {
	
	int[][] matrice;
	int ai;//card de E --> largeur de la matrice
	int s;//somme des elt de E --> longueur de la matrice
	MultiEnsemble E;//multiensemble a traiter
	UFind find;
	
	/**
	 * Contruits une matrice en fonction du Multiensemble passe en argument
	 * @param E MultiEnsemble qui est une ArrayList contenant les elements de l'ensemble
	 */
	public Matrice(MultiEnsemble E)
	{
		this.E=E;
		this.ai=E.ensemble.size();
		this.s=E.somme()+1;
		matrice=new int[ai][s];
	}
	
	public Matrice(MultiEnsemble E,UFind find)
	{
		this.E=E;
		this.ai=E.ensemble.size();
		this.s=E.somme()+1;
		this.find=find;
		matrice=new int[ai][s];
	}
	
	
	/**
	 * Affiche une matrice
	 */
	public void affiche()
	{
		System.out.print("        ");
		for(int i=0;i<s;i++) System.out.printf("%4d ",i);
		System.out.print("\n");
		for(int j=0;j<ai;j++)
		{
			System.out.printf("%4d -- ",E.ensemble.get(j)%10);
			for(int i=0;i<s;i++)
			{
				System.out.printf("%4d ",matrice[j][i]);
			}
			System.out.print("\n");
		}
		System.out.print("\n");
	}
	
	/**
	 * Rempli la matrice selon l'ensemble E qui est un multiEnsemble
	 */
	public void remplir_matrice()
	{

		for(int i=0;i<s;i++)
		{
			int j=0;
			while(j<ai)
			{
				int soustract=i-E.ensemble.get(j);
				
				if(soustract==0)
				{
					for(;j<ai;j++)
					{
						matrice[j][i]=1;
					}
				}
				else if(soustract<0)
				{
					matrice[j][i]=0;
				}
				else if(soustract>0)
				{
					int k=j-1;
					if(k>=0)
					{
						int un=matrice[k][soustract];
						matrice[j][i]=un;
						if(un==1)
						{
							for(;j<ai;j++)
							{
								matrice[j][i]=1;
							}
						}
					}
					else
						matrice[j][i]=0;
				}
				j++;
			}
		}
	}
	
	/**
	 * Fonction récursive qui pour un nombre "res_somme" donne les nombres appartenant à E tel que leur somme vaut res_somme
	 * @param res_somme nombre dont on veut calculer les sous ensembles {x1,...,xn} tel xi€E et la somme vaut res_somme
	 * @param resultat sert a savoir tout au long des appels recursifs quel nombre au veut calculer, res_somme vaut resultat au debut(va servir pour faire un bel affichage)
	 * @param tab tableau d'entier 0 ou 1, 1 à l'indice i si l'entier E.ensemble[i] fait parti de la somme, 0 sinon
	 * @param indice correspond au nombre d'elements qu'on prend dans E
	 * @param deja_ecrit booleen qui dit si on a deja ecrit "somme a "+resultat
	 */
	public boolean parcours(int res_somme,int resultat,int[] tab,int indice, boolean deja_ecrit)
	{
		int x;
		for(int i=0;i<indice;i++)
		{
			if(matrice[i][res_somme]==1)
			{
				x=res_somme-E.ensemble.get(i);
				if(x>0)
				{
					tab[i]=1;
					deja_ecrit=parcours(x,resultat,tab,i,deja_ecrit);
					tab[i]=0;
				}
				else if(x==0)
				{
					tab[i]=1;
					if(deja_ecrit==false)
					{
						System.out.print("\nsomme a "+resultat+": ");
					}
					this.affiche(tab);
					deja_ecrit=true;
					tab[i]=0;
				}
			}
		}
		return deja_ecrit;
	}
	
	/**
	 * Affiche les elements d'un tableau binaire de taille ai
	 */
	public void affiche(int[] tab)
	{
		for(int i =0;i<ai;i++)
			System.out.print(tab[i]);
		System.out.print(" ");
	}
	
	/**
	 * Fait appel a parcours() pour afficher toutes les enumerations possibles a partir de E (un MultiEnsemble)
	 */
	public void Enumeration()
	{
		int[] tab=new int[ai];
		for(int i=1;i<s;i++)
		{
			parcours(i,i,tab,ai,false);
		}
	}
	
	/**
	 * Fonction récursive qui pour un nombre "res_somme" donne les nombres appartenant à E tel que leur somme vaut res_somme
	 * @param res_somme nombre dont on veut calculer les sous ensembles {x1,...,xn} tel xi€E et la somme vaut res_somme
	 * @param resultat sert a savoir tout au long des appels recursifs quel nombre au veut calculer, res_somme vaut resultat au debut(va servir pour faire un bel affichage)
	 * @param tab tableau d'entier 0 ou 1, 1 à l'indice i si l'entier E.ensemble[i] fait parti de la somme, 0 sinon
	 * @param indice correspond au nombre d'elements qu'on prend dans E
	 * @param deja_ecrit booleen qui dit si on a deja ecrit "somme a "+resultat
	 */
	public void parcours2(int res_somme,int resultat,int[] tab,int indice)
	{
		int x;
		for(int i=0;i<indice;i++)
		{
			if(matrice[i][res_somme]==1)
			{
				x=res_somme-E.ensemble.get(i);
				if(x>0)
				{
					tab[i]=1;
					parcours2(x,resultat,tab,i);
					tab[i]=0;
				}
				else if(x==0)
				{
					tab[i]=1;
					find.une_solution(tab);
					tab[i]=0;
				}
			}
		}
	}
	
	public void Enumeration2()
	{
		int[] tab=new int[ai];
		int[] tab1=new int[ai];
		for(int i=0;i<ai;i++) tab1[i]=0;
		
		System.out.println("Les solutions de l'equation par poids croissants sont:");
		find.une_solution(tab1);
		for(int i=0;i<s;i++)
		{
			parcours2(i,i,tab,ai);
		}
	}
	
	
}
